Viterbi decoding is a technique used for a received data stream that has been encoded by a particular convolution, and assumes the most likely data based on the rules of the convolution to thereby decode the received data stream. The convolution rules can be expressed as a state transition diagram. With the concept of time taken into consideration in addition to the state transition diagram, they can be expressed as a trellis diagram.
FIG. 1 shows an example of a convolutional encoder, and FIG. 2 shows a trellis diagram thereof. In FIG. 1, reference numerals 81 and 82 denote delay elements, and 83 and 84 denote adders. The delay elements 81 and 82 each hold a value from one time segment ago. In FIG. 2, k denotes the time. Thus, FIG. 2 shows the state transition from time k−1 to time k, and that from time k to time k+1. In FIG. 2, S0 to S3 are state numbers in the state transitions. Each line is called a branch extending from one state to another state, the transition to which is possible.
In Viterbi decoding, in order to evaluate the likelihood (probability) of each transition from each state, the branch metric is calculated for each branch by using an evaluation function. Since the start of a decoding process, each state stores the cumulative branch metric of the most likely one of the branches leading to the state. This is called a path metric. Normally, a branch metric is calculated as the square error between the ideal value and the actually received value, and it is determined that the most likely branch is the one for which the addition between the path metric at time k−1 and the branch metric at time k yields the smallest value.
A path memory circuit holds an ideal value that takes a transition represented by the most likely branch at each time segment, and shifts the value to subsequent stages over time. At the time of the shift operation, each storage circuit selects and holds a value from a storage element circuit of a preceding stage along the most likely branch. For example, if at a given point in time the most likely branch for S0 is the branch for a transition thereto from S1, then, M0(i)=M1(i−1). In the expression, M0(x) is the value of the memory in the xth stage for state 0, M1(x) is the value of the memory in the xth stage for state 1, and i is an integer in the range from 1 to the number of path memory stages minus 1.
A path, obtained through such a process, that extends through the most likely branches at different points in time is called a survivor path. While each state in a trellis diagram has its survivor path, the survivor paths of all states converge into a single path as the decoding process proceeds. Similarly, as the shift operation proceeds, the values of the path memory circuit for each state converge into a single value. The obtained single survivor path is the final decoding result of the Viterbi decoding process.
As can be seen from the above description, a sufficient number of memory stages (memory length) of a path memory circuit is such a number that it is possible to hold all data occurring until the decoded results converge into one. However, the amount of time required until the convergence occurs varies depending not only on the encoding scheme and the application, but also on other environmental factors such as the temperature and the noise, and it is not possible to uniquely determine such an amount of time. Therefore, a conventional path memory circuit for Viterbi decoding employs a large memory length taking environmental variations into consideration. This increases the circuit scale and the power consumption.
In view of this, another type of path memory circuits are widely proposed in the art, in which the memory length can be changed according to the status of the decoding process (see Patent Document 1 and Patent Document 2). For example, in a path memory circuit having a memory length of M (M is a positive integer) stages as shown in FIG. 3, the operation of the storage element circuits of the jth and subsequent stages may be stopped depending on how the decoding results are converging. Here, j is an integer where 0<j≦M. In FIG. 3, reference numeral 20 denotes a selection circuit for selecting an input signal according to the most likely branch determined for each state, reference numeral 21 denotes a storage element circuit for holding the output from the selection circuit 20, reference numeral 22 denotes a selective storage circuit, reference numeral 23 denotes a stage of storage circuit, and reference numeral 24 denotes an output selection circuit.
When receiving a memory length control signal, which instructs to stop the jth and subsequent storage circuits 23, the operation of the jth and subsequent storage circuits 23 is stopped by, for example, stopping the supply of the clock signal thereto. In order to normally take out the output from the path memory circuit, the output selection circuit 24 selectively outputs the output of the storage circuit 23 of the j−1th stage according to the memory length control signal. Thus, the path memory circuit of FIG. 3 can operate by operating only the j−1th storage circuit 23, thereby cutting down the power consumption of M−j+1 storage circuits 23.
There is also a known approach in which the input stage to the path memory circuit is selected by allowing for early stages, instead of later stages, of the path memory circuit to be stopped (see Patent Document 3).
Patent Document 1: Japanese Laid-Open Patent Publication No. 63-166332
Patent Document 2: Japanese Laid-Open Patent Publication No. 10-302412
Patent Document 3: Japanese Laid-Open Patent Publication No. 2002-368628